// https://leetcode.cn/problems/maximum-subarray/description/

// 算法思路总结：
// 1. 使用Kadane算法求解最大子数组和
// 2. 维护当前子数组和，遇到负数时重置
// 3. 实时更新全局最大和
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <climits>

class Solution 
{
public:
    int maxSubArray(vector<int>& nums) 
    {
        int m = nums.size();
        int ret = INT_MIN;
        int cur = 0;
        
        for (int i = 0 ; i < m ; i++)
        {
            cur = max(cur + nums[i], nums[i]);
            ret = max(ret, cur);
        }
        
        return ret;
    }
};

int main()
{
    vector<int> v1 = {-2,1,-3,4,-1,2,1,-5,4}, v2 = {5,4,-1,7,8};
    Solution sol;

    cout << sol.maxSubArray(v1) << endl;
    cout << sol.maxSubArray(v2) << endl;

    return 0;
}